package 链表;
/**
 * https://leetcode-cn.com/problems/reverse-linked-list-ii/
 */
public class _92_反转链表2 {
    public class ListNode {
       int val;
       ListNode next;
       ListNode() {}
       ListNode(int val) { this.val = val; }
       ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }

    //记录最后一个节点的下一个节点,反转后头节点可能不是最后一个节点
    private ListNode suc = null;

    public ListNode reverseBetween(ListNode head, int left, int right) {
        //左区间为1，相当于反转前right个节点
        if(left == 1){
            return reverseN(head,right);
        }
        //如果左区间不为1，递归前进找到左区间为1的情况,那么就变成base case 反转前n个节点了
        //如果以head.next为起点，则反转区间就是[m-1,n-1]
        head.next = reverseBetween(head.next,left-1,right - 1);
        return head;
    }

    //函数定义:反转前n个节点,返回反转后的头节点
    private ListNode reverseN(ListNode head,int n){
        // 现在 head 节点在递归反转之后不一定是最后一个节点了，所以要记录后驱 successor（第 n + 1 个节点），
        // 反转之后将 head 连接上。
        if(n == 1){
            suc = head.next;
            return head;
        }
        //从头节点的下一个开始，则需要反转n-1个节点
        ListNode newHead = reverseN(head.next,n-1);
        //连接到新的头
        head.next.next = head;
        //将头节点连接到记录的后继节点
        head.next = suc;
        return newHead;
    }
}
